package cn.zzf.algs.note.exercise.fundamental;

import java.util.Iterator;
import java.util.Spliterator;
import java.util.function.Consumer;

/**
 * 栓相对列队
 * @author GaoFeng
 * @date 2019/11/29 15:24
 */
public class Deque<T> implements Iterable<T> {

    /** 当前容器内的元素数量 */
    private int size;

    /** 头结点 */
    private Node<T> first;

    /** 尾节点 */
    private Node<T> last;

    private boolean isEmpty;


    public int size() {
        return this.size;
    }

    public void pushLeft(T element)  {
        if (first == null) {
            initFirst(element);
        } else {
            if (first == last) {
                // 特殊处理单节点的情况, 直接更新首节点
                resetFirst(element);
            } else {
                // 更新first，只更新节点值，不更新节点对象
                T beforeElement = first.element;
                first.next = new Node<>(first, first.next, beforeElement);
                first.next.next.previous = first.next;
                first.element = element;
            }

        }
        size++;
    }



    public void pushRight(T element) {

        if(first == null) {
            initFirst(element);
        } else {
            // 特殊处理单节点的情况, 直接更新尾节点
            if (first == last) {
                this.resetLast(element);
            } else {
                // 更新last, 只更新节点值，不更新节点对象
                T beforeElement = last.element;
                last.previous = new Node<>(last.previous, last, beforeElement);
                last.previous.previous.next = last.previous;
                last.element = element;
            }

        }

        size++;
    }

    private void resetLast(T element) {
        // 此时根节点与尾节点是相同的
        last = new Node<>(first, first, element);
        first.previous = last;
        first.next = last;
    }

    private void resetFirst(T element) {
        first = new Node<>(last, last, element);
        last.previous = first;
        last.next = first;
    }

    private void initFirst(T element) {
        Node<T> node = new Node<>(element);
        first = node;
        last = node;
    }




    public T popLeft(){
        if (first == null ) {
            return null;
        }

        T element = first.element;

        // 单节点，需要将last也删除
        if (first == last) {
            first = null;
            last = null;
        } else {
            // 获取下一个节点的值
            first.element = first.next.element;
            first.next = first.next.next;
            // 更新下个节点的previous
            // first.next.previous = first;
        }

        size--;

        return element;
    }

    public T popRight() {

        if (first == null) {
            return null;
        }

        T element = last.element;

        // 单节点，需要将last也删除
        if (first == last) {
            first = null;
            last = null;
        } else {
            // 获取上一个节点的值
            last.element = last.previous.element;
            last.previous = last.previous.previous;
            // 更新下个节点的next
            // last.previous.next = last;
        }

        size--;

        return element;

    }


    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {

            private Node<T> currentNode = first;

            @Override
            public boolean hasNext() {
                return currentNode != null;
            }

            @Override
            public T next() {

                if (currentNode == last) {
                    T element = currentNode.element;
                    currentNode = null;
                    return element;
                }

                if (currentNode != null) {
                    T element = currentNode.element;
                    currentNode = currentNode.next;
                    return element;
                }

                return null;
            }
        };
    }

    @Override
    public void forEach(Consumer<? super T> action) {
    }

    @Override
    public Spliterator<T> spliterator() {
        return null;
    }

    static class Node<T> {

        /** 当前节点的上一个节点 */
        Node<T> previous;

        /** 当前节点的下一个节点 */
        Node<T> next;

        /** 当前节点的元素值  */
        T element;

        Node(T element) {
            this.element = element;
            this.previous = this;
            this.next = this;
        }

        Node(Node<T> previous, Node<T> next, T element) {
            this.previous = previous;
            this.next = next;
            this.element = element;
        }
    }
}
